import java.util.Arrays;

public class O04 {
    public static void main(String[] args) {
        O04 o = new O04();
        System.out.println(o.findNumberIn2DArray(new int[][]{
                {1,   4,  7, 11, 15},
                {2,   5,  8, 12, 19},
                {3,   6,  9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        },5));
    }

    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int[] mid ={matrix.length/2,matrix[0].length/2},l = {0,0},h = {matrix.length-1,matrix[0].length-1};
        while (getValue(l,matrix)<getValue(h,matrix)){
            if (matrix[mid[0]][mid[1]]==target)
                return true;
            if (matrix[mid[0]][mid[1]]<target){
                if (mid[0]<matrix.length-1)
                    l[0] = mid[0]+1;
                else {
                    l[0] = 0;
                    l[1] = mid[1]+1;
                }
            }else {
                if (mid[0]>0)
                    h[0] = mid[0]-1;
                else {
                    h[0] = matrix.length-1;
                    l[1] = mid[1]-1;
                }
            }
            mid = getMid(l,h,matrix);
        }
        return false;
    }
    public int[] getMid(int[] low,int[] high,int[][] matrix){
        int n = matrix.length; //一列有多少个
        int l1 = n*low[1]+low[0];
        int l2 = n*high[1]+high[0];
        int mid = (l1+l2)/2;
        int[] re = new int[2];
        re[0] = mid%n;
        if (re[0]==0)
            re[1] = mid/n;
        else re[1] = mid/n+1;
        return re;
    }
    public int getValue(int[] a,int[][] matrix){
        int n = matrix.length; //一列有多少个
        return n*a[1]+a[0];
    }
}
